{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Coordinate With Maximum Network Quality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bestCoordinate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网络信号最好的坐标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>towers</code>&nbsp;和一个整数 <code>radius</code> 。</p>\n",
    "\n",
    "<p>数组&nbsp; <code>towers</code>&nbsp; 中包含一些网络信号塔，其中&nbsp;<code>towers[i] = [x<sub>i</sub>, y<sub>i</sub>, q<sub>i</sub>]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个网络信号塔的坐标是&nbsp;<code>(x<sub>i</sub>, y<sub>i</sub>)</code>&nbsp;且信号强度参数为&nbsp;<code>q<sub>i</sub></code><sub>&nbsp;</sub>。所有坐标都是在&nbsp; X-Y 坐标系内的&nbsp;<strong>整数</strong>&nbsp;坐标。两个坐标之间的距离用 <strong>欧几里得距离</strong>&nbsp;计算。</p>\n",
    "\n",
    "<p>整数&nbsp;<code>radius</code>&nbsp;表示一个塔 <strong>能到达&nbsp;</strong>的 <strong>最远距离</strong>&nbsp;。如果一个坐标跟塔的距离在 <code>radius</code>&nbsp;以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 <code>radius</code>&nbsp;以外的距离该塔是 <strong>不能到达的</strong>&nbsp;。</p>\n",
    "\n",
    "<p>如果第 <code>i</code>&nbsp;个塔能到达 <code>(x, y)</code>&nbsp;，那么该塔在此处的信号为&nbsp;<code>⌊q<sub>i</sub> / (1 + d)⌋</code>&nbsp;，其中&nbsp;<code>d</code>&nbsp;是塔跟此坐标的距离。一个坐标的 <b>信号强度</b> 是所有 <strong>能到达&nbsp;</strong>该坐标的塔的信号强度之和。</p>\n",
    "\n",
    "<p>请你返回数组 <code>[c<sub>x</sub>, c<sub>y</sub>]</code> ，表示 <strong>信号强度</strong> 最大的 <strong>整数</strong> 坐标点&nbsp;<code>(c<sub>x</sub>, c<sub>y</sub>)</code> 。如果有多个坐标网络信号一样大，请你返回字典序最小的 <strong>非负</strong> 坐标。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>坐标&nbsp;<code>(x1, y1)</code>&nbsp;字典序比另一个坐标&nbsp;<code>(x2, y2)</code> 小，需满足以下条件之一：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>要么&nbsp;<code>x1 &lt; x2</code>&nbsp;，</li>\n",
    "\t\t<li>要么&nbsp;<code>x1 == x2</code> 且&nbsp;<code>y1 &lt; y2</code>&nbsp;。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li><code>⌊val⌋</code>&nbsp;表示小于等于&nbsp;<code>val</code>&nbsp;的最大整数（向下取整函数）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/17/untitled-diagram.png\" style=\"width: 176px; height: 176px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2\n",
    "<b>输出：</b>[2,1]\n",
    "<strong>解释：</strong>\n",
    "坐标 (2, 1) 信号强度之和为 13\n",
    "- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7\n",
    "- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2\n",
    "- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4\n",
    "没有别的坐标有更大的信号强度。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>towers = [[23,11,21]], radius = 9\n",
    "<b>输出：</b>[23,11]\n",
    "<strong>解释：</strong>由于仅存在一座信号塔，所以塔的位置信号强度最大。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2\n",
    "<b>输出：</b>[1,2]\n",
    "<strong>解释：</strong>坐标 (1, 2) 的信号强度最大。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= towers.length &lt;= 50</code></li>\n",
    "\t<li><code>towers[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub>, q<sub>i</sub> &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= radius &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [coordinate-with-maximum-network-quality](https://leetcode.cn/problems/coordinate-with-maximum-network-quality/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [coordinate-with-maximum-network-quality](https://leetcode.cn/problems/coordinate-with-maximum-network-quality/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,5],[2,1,7],[3,1,9]]\\n2', '[[23,11,21]]\\n9', '[[1,2,13],[2,1,7],[0,1,9]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y-ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q/(1+d**0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        res_x = 0\n",
    "        res_y = 0\n",
    "        max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    res_x, res_y, max_quality = x, y, quality\n",
    "        return [res_x, res_y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        ans_x, ans_y, ans_sig = 0, 0, 0.0\n",
    "        n = len(towers)\n",
    "        for x in range(51):\n",
    "            for y in range(51):\n",
    "                sig = 0\n",
    "                for i in range(n):\n",
    "                    #d = ((x-towers[i][0])**2 + (y-towers[i][1])**2)**0.5\n",
    "                    d = math.hypot(x-towers[i][0], y-towers[i][1])\n",
    "                    if d<=radius:\n",
    "                        sig += int(towers[i][2]/(1+d))\n",
    "                    if sig>ans_sig:\n",
    "                        ans_x, ans_y, ans_sig = x, y, sig\n",
    "        return [ans_x, ans_y] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        def d(t1, t2):\n",
    "            return sqrt(pow(t1[0]-t2[0], 2) + pow(t1[1]-t2[1], 2))\n",
    "        mx, my, m = 0, 0, -1\n",
    "        for i in range(51):\n",
    "            for j in range(51):\n",
    "                cur = 0\n",
    "                for t in towers:\n",
    "                    du = d([i, j], t)\n",
    "                    if du<=radius:\n",
    "                        cur += int(t[2]/(1+du))\n",
    "                if cur>m:\n",
    "                    mx, my, m = i, j, cur\n",
    "        return [mx, my]\n",
    "\n",
    "        # ans, mx = -1, -1\n",
    "        # for i in range(len(towers)):\n",
    "        #     cur = 0\n",
    "        #     for j in range(len(towers)):\n",
    "        #         du = d(towers[i], towers[j])\n",
    "        #         if du<=radius:\n",
    "        #             cur += int(towers[j][2]/(1+du))\n",
    "        #     if cur>mx or cur == mx and (towers[i][0]<towers[ans][0] or towers[i][0]==towers[ans][0] and towers[i][1]<towers[ans][1]):\n",
    "        #         ans = i\n",
    "        #         mx = cur\n",
    "        # return towers[ans][:2] if mx>0 else [0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        ans = [0,0]\n",
    "        res = 0\n",
    "        for i in range(51):\n",
    "            for j in range(51):\n",
    "                sum_ = 0\n",
    "                for x,y,q in towers:\n",
    "                    if (x-i)**2 + (y-j)**2 <= radius**2:\n",
    "                        r = math.sqrt((x-i)**2 + (y-j)**2) + 1\n",
    "                        sum_ += int(q/r)\n",
    "                if sum_ > res:\n",
    "                    res = sum_\n",
    "                    ans = [i,j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        mx = 0\n",
    "        ans = [0, 0]\n",
    "        for i in range(51):\n",
    "            for j in range(51):\n",
    "                t = 0\n",
    "                for x, y, q in towers:\n",
    "                    d = ((x - i) ** 2 + (y - j) ** 2) ** 0.5\n",
    "                    if d <= radius:\n",
    "                        t += floor(q / (1 + d))\n",
    "                if t > mx:\n",
    "                    mx = t\n",
    "                    ans = [i, j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        # 初始化最大信号强度和最佳坐标\n",
    "        max_signal = -1\n",
    "        best_coord = [0, 0]\n",
    "        \n",
    "        # 遍历所有可能的坐标点\n",
    "        for x in range(0, 51):  # 给定数组中的坐标不会超过50\n",
    "            for y in range(0, 51):\n",
    "                # 对于每个坐标点，计算其信号强度\n",
    "                signal = 0\n",
    "                for tower in towers:\n",
    "                    d = ((tower[0]-x)**2 + (tower[1]-y)**2)**0.5\n",
    "                    if d <= radius:\n",
    "                        signal += tower[2] // (1 + d)\n",
    "                # 更新最大信号强度和最佳坐标\n",
    "                if signal > max_signal:\n",
    "                    max_signal = signal\n",
    "                    best_coord = [x, y]\n",
    "                    \n",
    "        return best_coord\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        grid = [[0]*51 for _ in range(51)]\n",
    "        for x, y, q in towers:\n",
    "            for i in range(max(0, x-radius), min(50, x+radius)+1):\n",
    "                for j in range(max(0, y-radius), min(50, y+radius)+1):\n",
    "                    if (x-i)**2 + (y-j)**2 <= radius**2:\n",
    "                        grid[i][j] += int(q / (1 + ((x-i)**2 + (y-j)**2)**0.5))\n",
    "        return max(((i, j) for i in range(51) for j in range(51)), key = lambda x : (grid[x[0]][x[1]], -x[0], -x[1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        min_x = min_y = 50\n",
    "        max_x = max_y = 0\n",
    "\n",
    "        for tower in towers:\n",
    "            min_x = min(min_x, tower[0])\n",
    "            min_y = min(min_y, tower[1])\n",
    "            max_x = max(max_x, tower[0])\n",
    "            max_y = max(max_y, tower[1])\n",
    "        \n",
    "        max_signal = 0\n",
    "        max_coor = [0, 0]\n",
    "        for i in range(min_x, max_x + 1):\n",
    "            for j in range(min_y, max_y + 1):\n",
    "                signal = 0\n",
    "                for tower in towers:\n",
    "                    d = math.sqrt((i - tower[0]) ** 2 + (j - tower[1]) ** 2)\n",
    "                    if d >  radius:\n",
    "                        continue\n",
    "                    signal += tower[2] // (1 + d)\n",
    "                if signal > max_signal:\n",
    "                    max_signal = signal\n",
    "                    max_coor = [i, j]\n",
    "        \n",
    "        return max_coor\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        ans_x, ans_y, ans_sig = 0, 0, 0.0\n",
    "        n = len(towers)\n",
    "        for x in range(51):\n",
    "            for y in range(51):\n",
    "                sig = 0\n",
    "                for i in range(n):\n",
    "                    d = ((x-towers[i][0])**2 + (y-towers[i][1])**2)**0.5\n",
    "                    if d<=radius:\n",
    "                        sig += int(towers[i][2]/(1+d))\n",
    "                    if sig>ans_sig:\n",
    "                        ans_x, ans_y, ans_sig = x, y, sig\n",
    "                    elif sig==ans_sig:\n",
    "                        if x<ans_x or (x==ans_x and y<ans_y):\n",
    "                            ans_x, ans_y = x, y\n",
    "        return [ans_x, ans_y] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        n = len(towers)\n",
    "        x_max = max([t[0] for t in towers])\n",
    "        y_max = max([t[1] for t in towers])\n",
    "        maxScore = 0\n",
    "        result = [0,0]\n",
    "        for x1 in range(x_max+1):\n",
    "            for y1 in range(y_max+1):\n",
    "                tScore = 0\n",
    "                for x2,y2,q2 in towers:\n",
    "                    d = (x1-x2)**2+(y1-y2)**2\n",
    "                    if(d <= radius**2):\n",
    "                        tScore += int(q2/(1+sqrt(d)))\n",
    "                if(tScore > maxScore):\n",
    "                    maxScore = tScore\n",
    "                    result = [x1,y1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        max_value = 0\n",
    "        ans = [0, 0]\n",
    "        for i in range(51):\n",
    "            for j in range(51):\n",
    "                temp = 0\n",
    "                for x, y, q in towers:\n",
    "                    d = ((x - i)**2 + (y - j)**2) ** 0.5\n",
    "                    if d <= radius:\n",
    "                        temp += floor(q / (1 + d))\n",
    "                if temp > max_value:\n",
    "                    max_value = temp\n",
    "                    ans = [i, j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        length = len(towers)\n",
    "        max_d = -1\n",
    "        res = [-1, -1]\n",
    "        for x in range(51):\n",
    "            for y in range(51):\n",
    "                d = 0\n",
    "                for j in range(length):\n",
    "                    distance = (x - towers[j][0]) ** 2 + (y - towers[j][1]) ** 2\n",
    "                    if distance > radius ** 2:\n",
    "                        continue\n",
    "                    d += towers[j][2] // (1 + distance ** 0.5)\n",
    "                if d > max_d:\n",
    "                    max_d = d\n",
    "                    res = [x, y]\n",
    "                elif d == max_d:\n",
    "                    if x < res[0] or (x == res[0] and y < res[1]):\n",
    "                        res = [x, y]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        ans = [[0 for _ in range(51)] for _ in range(51)]\n",
    "        for i in range(51):\n",
    "            for j in range(51):\n",
    "                for tower in towers:\n",
    "                    if abs(tower[0] - i) > radius or abs(tower[1] - j) > radius:\n",
    "                        continue\n",
    "                    dist = sqrt((tower[0] - i) ** 2 + (tower[1] - j) ** 2)\n",
    "                    if dist <= radius:\n",
    "                        ans[i][j] += floor(tower[2] / (dist + 1))\n",
    "        a = -1\n",
    "        b = -1\n",
    "        temp = -1\n",
    "        for i in range(51):\n",
    "            for j in range(51):\n",
    "                if ans[i][j] > temp:\n",
    "                    a = i\n",
    "                    b = j\n",
    "                    temp = ans[i][j]\n",
    "\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        (x1-x)^2 + (y1-y)^2 + ()\n",
    "        \"\"\"\n",
    "        x_max = max(tower[0] for tower in towers)\n",
    "        y_max = max(tower[1] for tower in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx)**2 + (y - ty)**2\n",
    "                    if d <= radius**2:\n",
    "                        quality += int(q / (1 + d**0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        towers.sort(key=lambda x:x[1])\n",
    "        towers.sort(key=lambda x:x[0])\n",
    "        res = [0, 0]\n",
    "        max_val = 0\n",
    "        for i in range(51):\n",
    "            for j in range(51):\n",
    "                now_sign = 0\n",
    "                for tower in towers:\n",
    "                    d = math.sqrt((i - tower[0]) ** 2 + (j - tower[1]) ** 2)\n",
    "                    if d <= radius:\n",
    "                        now_sign += math.floor(tower[2] / (1 + d))\n",
    "                if now_sign > max_val:\n",
    "                    res = [i, j]\n",
    "                    max_val = now_sign\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        # 暴力模拟题\n",
    "        # 找出坐标边界，即塔的最大x和y\n",
    "        x_max = max([t[0] for t in towers])\n",
    "        y_max = max([t[1] for t in towers])\n",
    "        res_x=res_y=max_xinhao = 0\n",
    "        # 遍历每一个坐标\n",
    "        for x in range(x_max+1):\n",
    "            for y in range(y_max+1):\n",
    "                cur_xinhao = 0\n",
    "                for i,j,q in towers:\n",
    "                    d = (x-i)**2+(y-j)**2\n",
    "                    if d <= radius**2:\n",
    "                        cur_xinhao += q//(1+d**0.5)\n",
    "                if cur_xinhao > max_xinhao:  # 大于才更新，保证最大值对应的是字典序最小的\n",
    "                    res_x = x\n",
    "                    res_y = y\n",
    "                    max_xinhao = cur_xinhao\n",
    "        return [res_x,res_y]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        towers_info = []\n",
    "        max_x = 0\n",
    "        min_x = 101\n",
    "        max_y = 0\n",
    "        min_y = 101\n",
    "        max_power = 0\n",
    "        for i in towers:\n",
    "            max_power = max_power + int(i[2])\n",
    "            if min_x > int(i[0]):\n",
    "                min_x = int(i[0])\n",
    "            if min_y > int(i[1]):\n",
    "                min_y = int(i[1])\n",
    "            if max_x < int(i[0]):\n",
    "                max_x = int(i[0])\n",
    "            if max_y < int(i[1]):\n",
    "                max_y = int(i[1])\n",
    "        real_x = 0\n",
    "        real_y = 0\n",
    "        real_power = 0\n",
    "        iii = 0\n",
    "        if max_power == 0:\n",
    "            return [0,0]\n",
    "        \n",
    "        for i in range(min_x,max_x+1):\n",
    "            for j in range(min_y,max_y+1):\n",
    "                k = 0\n",
    "                for tower in towers:\n",
    "                    d = (i-int(tower[0]))*(i-int(tower[0]))+(j-int(tower[1]))*(j-int(tower[1]))\n",
    "                    if sqrt(d) <= radius:\n",
    "                        k = k + int((int(tower[2]))/(1+sqrt(d)))\n",
    "                if max_power == k:\n",
    "                    xxx = []\n",
    "                    xxx.append(i)\n",
    "                    xxx.append(j)\n",
    "                    # print(k)\n",
    "                    return xxx\n",
    "                if k > real_power:\n",
    "                    real_power = k\n",
    "                    real_x = i\n",
    "                    real_y = j\n",
    "\n",
    "        xxx = []\n",
    "        xxx.append(real_x)\n",
    "        xxx.append(real_y)\n",
    "        # print(real_power)\n",
    "        return xxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        best_point = [0, 0, 0]\n",
    "        xMax = 0\n",
    "        yMax = 0\n",
    "        for tower in towers:\n",
    "            if tower[0] > xMax:\n",
    "                xMax = tower[0]\n",
    "            if tower[1] > yMax:\n",
    "                yMax = tower[1]\n",
    "        for x in range(xMax + 1):\n",
    "            for y in range(yMax + 1):\n",
    "                item = [x, y]\n",
    "                sum_power = 0\n",
    "                for i in towers:\n",
    "                    d = math.sqrt((item[0] - i[0]) ** 2 + (item[1] - i[1]) ** 2)\n",
    "                    if d > radius:\n",
    "                        continue\n",
    "                    else:\n",
    "                        sum_power += math.floor(i[2] / (1 + d))\n",
    "                if sum_power > best_point[2]:\n",
    "                    best_point = item + [sum_power]\n",
    "                elif sum_power == best_point[2]:\n",
    "                    if item[0] < best_point[0] or (item[0] == best_point[0] and item[1] < best_point[1]):\n",
    "                        best_point = item + [sum_power]\n",
    "        return best_point[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max([t[0] for t in towers])\n",
    "        y_max = max([t[1] for t in towers])\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max+1):\n",
    "            for  y in range(y_max+1):\n",
    "                quality = 0 \n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x-tx)**2 + (y-ty)**2\n",
    "                    if d<=radius**2:\n",
    "                        quality += int(q/(1+d**0.5))\n",
    "                    if quality>max_quality:\n",
    "                        cx, cy, max_quality = x, y,quality\n",
    "        return (cx, cy)        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        x_max = max(t[0] for t in towers)\n",
    "        y_max = max(t[1] for t in towers)\n",
    "        cx = cy = max_quality = 0\n",
    "        for x in range(x_max + 1):\n",
    "            for y in range(y_max + 1):\n",
    "                quality = 0\n",
    "                for tx, ty, q in towers:\n",
    "                    d = (x - tx) ** 2 + (y - ty) ** 2\n",
    "                    if d <= radius ** 2:\n",
    "                        quality += int(q / (1 + d ** 0.5))\n",
    "                if quality > max_quality:\n",
    "                    cx, cy, max_quality = x, y, quality\n",
    "        return [cx, cy]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        n = len(towers)\n",
    "        x_max = max([t[0] for t in towers])\n",
    "        y_max = max([t[1] for t in towers])\n",
    "        maxScore = 0\n",
    "        result = [0,0]\n",
    "        for x1 in range(x_max+1):\n",
    "            for y1 in range(y_max+1):\n",
    "                tScore = 0\n",
    "                for x2,y2,q2 in towers:\n",
    "                    d = (x1-x2)**2+(y1-y2)**2\n",
    "                    if(d <= radius**2):\n",
    "                        tScore += int(q2/(1+sqrt(d)))\n",
    "                if(tScore > maxScore):\n",
    "                    maxScore = tScore\n",
    "                    result = [x1,y1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        m = len(towers)\n",
    "        n = len(towers[0])\n",
    "        row, col = 0, 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                row = max(row, towers[i][1])\n",
    "            col = max(col, towers[i][0])\n",
    "        matrix = [[0] * (col + 1) for _ in range(row + 1)]\n",
    "        max_x = 0\n",
    "        max_y = 0\n",
    "        max_intensity = 0\n",
    "        for x in range(col+1):\n",
    "            for y in range(row+1):\n",
    "                # x = q\n",
    "                # y = row - p\n",
    "                s = 0\n",
    "                for k in range(len(towers)):\n",
    "                    dis = (towers[k][0] - x) ** 2 + (towers[k][1] - y) ** 2\n",
    "                    if dis <= radius ** 2:\n",
    "                        intensity = int(towers[k][2] / (1 + dis ** 0.5))\n",
    "                        s += intensity\n",
    "                if s > max_intensity:\n",
    "                    max_x = x\n",
    "                    max_y = y\n",
    "                    max_intensity = s\n",
    "                    # print(x, y, max_intensity)\n",
    "        return [max_x, max_y]\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        def signal(tower, x, y):\n",
    "            d = ((x - tower[0]) ** 2 + (y - tower[1]) ** 2) ** 0.5\n",
    "            return int(tower[2] / (1 + d)) if d <= radius else 0\n",
    "\n",
    "        x_max = max(tower[0] for tower in towers)\n",
    "        x_min = min(tower[0] for tower in towers)\n",
    "        y_max = max(tower[1] for tower in towers)\n",
    "        y_min = min(tower[1] for tower in towers)\n",
    "        x_range = range(x_min, x_max + 1)\n",
    "        y_range = range(y_min, y_max + 1)\n",
    "        max_signal = 0\n",
    "        max_x, max_y = 0, 0\n",
    "        for x in x_range:\n",
    "            for y in y_range:\n",
    "                signal_sum = sum(signal(tower, x, y) for tower in towers)\n",
    "                if signal_sum > max_signal:\n",
    "                    max_signal = signal_sum\n",
    "                    max_x, max_y = x, y\n",
    "        return [max_x, max_y]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        xdir = {}\n",
    "        max_ = [0,[0,0]]\n",
    "        for x,y,qi in towers:\n",
    "            for i in range(max(x-radius,0),x+1):\n",
    "                for j in range(max(y-radius,0),y+1):\n",
    "                    if i not in xdir:\n",
    "                        xdir[i] = set()\n",
    "                    if j not in xdir[i]:\n",
    "                        q = 0\n",
    "                        for m,n,k in towers:\n",
    "                            d = ((i-m)**2+(j-n)**2)**0.5\n",
    "                            if d <= radius:\n",
    "                                q += int(k/(1+d))\n",
    "                        if q>max_[0]:\n",
    "                            max_ = [q,[i,j]]\n",
    "                        elif q==max_[0]:\n",
    "                            max_.append([i,j])\n",
    "                        xdir[i].add(j)\n",
    "        max_ = max_[1:]\n",
    "        max_.sort()\n",
    "        return max_[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        \n",
    "        ans = [[0]*101 for _ in range(101)]\n",
    "        for x, y, q in towers:\n",
    "            for i in range(101):\n",
    "                for j in range(101):\n",
    "                    dis = ((x-i)**2+(y-j)**2)**0.5\n",
    "                    if dis <= radius:\n",
    "                        ans[i][j] += q//(1+dis)\n",
    "                        \n",
    "        ceil = max(max(ls) for ls in ans)\n",
    "\n",
    "        for i in range(101):\n",
    "            for j in range(101):\n",
    "                if ans[i][j] == ceil:\n",
    "                    return [i, j]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "      ans = [0, 0, 0]\n",
    "      n = len(towers)\n",
    "      radius *= radius\n",
    "      for i in range(101):\n",
    "        for j in range(101):\n",
    "          cnt = 0\n",
    "          for k in range(n):\n",
    "            dis = (towers[k][0] - i) ** 2 + (towers[k][1] - j) ** 2\n",
    "            if dis <= radius:\n",
    "              cnt += towers[k][2] // (1 + dis ** 0.5)\n",
    "          if cnt > ans[2]:\n",
    "            ans = [i, j, cnt]\n",
    "      \n",
    "      return ans[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        min_x = min_y = 50\n",
    "        max_x = max_y = 0\n",
    "\n",
    "        for tower in towers:\n",
    "            min_x = min(min_x, tower[0])\n",
    "            min_y = min(min_y, tower[1])\n",
    "            max_x = max(max_x, tower[0])\n",
    "            max_y = max(max_y, tower[1])\n",
    "        \n",
    "        max_signal = 0\n",
    "        max_coor = [0, 0]\n",
    "        for i in range(min_x, max_x + 1):\n",
    "            for j in range(min_y, max_y + 1):\n",
    "                signal = 0\n",
    "                for tower in towers:\n",
    "                    d = math.sqrt((i - tower[0]) ** 2 + (j - tower[1]) ** 2)\n",
    "                    if d >  radius:\n",
    "                        continue\n",
    "                    signal += tower[2] // (1 + d)\n",
    "                if signal > max_signal:\n",
    "                    max_signal = signal\n",
    "                    max_coor = [i, j]\n",
    "        \n",
    "        return max_coor\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        n = len(towers)\n",
    "        x = [i for i in range(n)]\n",
    "        y = [i for i in range(n)]\n",
    "        x.sort(key=lambda a: towers[a][0])\n",
    "        y.sort(key=lambda a: towers[a][1])\n",
    "        xmax, xmin, ymax, ymin = towers[x[-1]][0], towers[x[0]][0], towers[y[-1]][1], towers[y[0]][1]\n",
    "        def distance(a, b):\n",
    "            return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5\n",
    "        def sign(q, d):\n",
    "            return int(q / (1 + d))\n",
    "        def judge(a, b):\n",
    "            if a[0] < b[0]:\n",
    "                return a\n",
    "            elif a[0] == b[0]:\n",
    "                if a[1] < b[1]:\n",
    "                    return a\n",
    "                elif a[1] > b[0]:\n",
    "                    return b\n",
    "            return b\n",
    "        ans = [0, 0]\n",
    "        res = 0\n",
    "        for x in range(xmin, xmax+1):\n",
    "            for y in range(ymin, ymax+1):\n",
    "                s = 0\n",
    "                for j in towers:\n",
    "                    d = distance([x, y], j[:2])\n",
    "                    if d <= radius:\n",
    "                        s += sign(j[2], d)\n",
    "                if s > res:\n",
    "                    res = max(res, s)\n",
    "                    ans = [x, y]\n",
    "                elif s == res:\n",
    "                    res = max(res, s)\n",
    "                    ans = judge(ans, [x, y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        xmin = 50\n",
    "        xmax = 0\n",
    "        ymin = 50\n",
    "        ymax = 0 \n",
    "        for i in range(len(towers)):\n",
    "            xmin = min(xmin,towers[i][0])\n",
    "            xmax = max(xmax,towers[i][0])\n",
    "            ymin = min(ymin,towers[i][1])\n",
    "            ymax = max(ymax,towers[i][1])\n",
    "\n",
    "        ans = 0\n",
    "        xpos = 0\n",
    "        ypos = 0\n",
    "        for i in range(xmin,xmax+1):\n",
    "            for j in range(ymin,ymax+1):\n",
    "                power = 0\n",
    "                for k in range(len(towers)):\n",
    "                    dis = sqrt((towers[k][0]-i)**2+(towers[k][1]-j)**2)\n",
    "                    if dis<=radius:\n",
    "                        power+=int(towers[k][2]/(1+dis))\n",
    "                # print(power,ans)\n",
    "                if ans < power:\n",
    "                    xpos = i \n",
    "                    ypos = j\n",
    "                    ans = power \n",
    "        return [xpos,ypos]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], k: int) -> List[int]:\n",
    "        g = [[0] * 110 for _ in range(110)]\n",
    "        x, y, val = 0, 0, 0\n",
    "        for (a, b, q) in towers:\n",
    "            for i in range(max(0, a - k), a + k + 1):\n",
    "                for j in range(max(0, b - k), b + k + 1):\n",
    "                    d = math.sqrt((a - i) * (a - i) + (b - j) * (b - j))\n",
    "                    if d > k:\n",
    "                        continue\n",
    "                    g[i][j] += int(q / (1 + d))\n",
    "                    if g[i][j] > val:\n",
    "                        val, x, y = g[i][j], i, j\n",
    "                    elif g[i][j] == val and ((i < x or (i == x and j < y))):\n",
    "                        x, y = i, j\n",
    "        return [x, y]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], r: int) -> List[int]:\n",
    "                    \n",
    "                n = len(towers)\n",
    "                power = 0;c1,c2 = 0,0\n",
    "                for x in range(51):\n",
    "                    for y in range(51):\n",
    "                        tot = 0\n",
    "                        for i,(x1,y1,q1) in enumerate(towers):\n",
    "                            d = (x-x1)**2 + (y1-y)**2\n",
    "                            if d > r**2:continue\n",
    "                            tot += (q1 ) // (1 + sqrt(d))\n",
    "                       \n",
    "                        if tot > power:\n",
    "                            power = tot\n",
    "                            c1,c2 = x,y\n",
    "                        elif tot == power and (c1 > x or (c1 == x and c2 > y)):\n",
    "                            c1,c2 = x,y\n",
    "                return [c1,c2]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        nums = [[0] * 101 for _ in range(101)]\n",
    "        for x1 in range(101):\n",
    "            for y1 in range(101):\n",
    "                for x2, y2, q in towers:\n",
    "                    d2 = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)\n",
    "                    if d2 <= radius * radius:\n",
    "                        nums[x1][y1] += q//(1+sqrt(d2))\n",
    "        mx = 0\n",
    "        ans = [0, 0]\n",
    "        for i in range(101):\n",
    "            for j in range(101):\n",
    "                if nums[i][j] > mx:\n",
    "                    mx = nums[i][j]\n",
    "                    ans = [i, j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math \n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], r: int) -> List[int]:\n",
    "        ans = []\n",
    "        def f(x, y):\n",
    "            a = 0 \n",
    "            for x1, y1, q in towers:\n",
    "                d = (x-x1)**2 + (y-y1)**2 \n",
    "                if d <= r**2:\n",
    "                    a += int(q/(1 + math.sqrt(d)) )\n",
    "            return [-a, x, y] \n",
    "        for x in range(51):\n",
    "            for y in range(51):\n",
    "                ans.append(f(x, y)) \n",
    "        ans.sort()\n",
    "        return ans[0][1:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        nums = [[0] * 101 for _ in range(101)]\n",
    "        for x1 in range(101):\n",
    "            for y1 in range(101):\n",
    "                for x2, y2, q in towers:\n",
    "                    d2 = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)\n",
    "                    if d2 <= radius * radius:\n",
    "                        nums[x1][y1] += q//(1+sqrt(d2))\n",
    "        mx = 0\n",
    "        ans = [0, 0]\n",
    "        for i in range(101):\n",
    "            for j in range(101):\n",
    "                if nums[i][j] > mx:\n",
    "                    mx = nums[i][j]\n",
    "                    ans = [i, j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        for x in range(51):\n",
    "            for y in range(51):\n",
    "                count = 0\n",
    "                for tower in towers:\n",
    "                    d = math.sqrt((x - tower[0]) ** 2 + (y - tower[1]) ** 2)\n",
    "            \n",
    "                    if d <= radius:\n",
    "                        count += (tower[2] // (1 + d))\n",
    "\n",
    "                \n",
    "                dic[count].append([x, y])\n",
    "        \n",
    "        for key, value in dic.items():\n",
    "            if key == max(dic.keys()) :\n",
    "                value.sort()\n",
    "                return value[0]                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        for x in range(51):\n",
    "            for y in range(51):\n",
    "                count = 0\n",
    "                for tower in towers:\n",
    "                    d = math.sqrt((x - tower[0]) ** 2 + (y - tower[1]) ** 2)\n",
    "            \n",
    "                    if d <= radius:\n",
    "                        count += (tower[2] // (1 + d))\n",
    "\n",
    "                \n",
    "                dic[count].append([x, y])\n",
    "        \n",
    "        print(dic)\n",
    "        for key, value in dic.items():\n",
    "            if key == max(dic.keys()) :\n",
    "                value.sort()\n",
    "                return value[0]                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        # towers.sort()\n",
    "        max_q = 0\n",
    "        xq, yq = -1, -1\n",
    "        datas = {}\n",
    "        import math\n",
    "        for xi, yi, qi in towers:\n",
    "            x_s = max(0, xi-radius)\n",
    "            x_e = xi+radius+1\n",
    "            y_s = max(0, yi-radius)\n",
    "            y_e = yi+radius+1\n",
    "            for xc in range(x_s, x_e):\n",
    "                dx = xi-xc\n",
    "                for yc in range(y_s, y_e):\n",
    "                    dy = yi-yc\n",
    "                    d2 = dx*dx+dy*dy\n",
    "                    if d2>radius*radius:\n",
    "                        continue\n",
    "                    q = int(qi/(1+math.sqrt(d2)))\n",
    "                    new_q = datas.get((xc, yc), 0) + q\n",
    "                    datas[(xc, yc)] = new_q\n",
    "                    if new_q>max_q:\n",
    "                        xq, yq = xc, yc\n",
    "                        max_q = new_q\n",
    "                        # print('update', max_q, xq, yq)\n",
    "                    elif new_q==max_q:\n",
    "                        if xc<xq or (xc==xq and yc<yq):\n",
    "                            xq, yq = xc, yc\n",
    "                            max_q = new_q\n",
    "        xq, yq = max(0, xq), max(0, yq)\n",
    "        print(datas)\n",
    "        return [xq, yq]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        map = defaultdict(int)\n",
    "        # 以塔为中心搜索\n",
    "        for x, y, q in towers:\n",
    "            for x2 in range(max(0, x-radius), x+radius+1):\n",
    "                for y2 in range(max(0, y-radius), y+radius+1):\n",
    "                    d = sqrt((x-x2) * (x-x2) + (y-y2) * (y-y2))\n",
    "                    if d <= radius:\n",
    "                        map[(x2, y2)] += q // (1 + d)\n",
    "        \n",
    "        mx = 0\n",
    "        ans = (inf, inf)\n",
    "        for k, v in map.items():\n",
    "            if v > mx or v == mx and k < ans:\n",
    "                mx = v\n",
    "                ans = k\n",
    "        return ans if mx else (0, 0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:\n",
    "        # 1所有可能达到的点的坐标范围（-50，-50）-（100，100）\n",
    "        2# 所以便利这个矩形内的所有点，累加这个点的所有信号强度，然后比较出最大信号强度的坐标即可\n",
    "        hashmap=collections.defaultdict(int)\n",
    "        max_q=0\n",
    "        for x,y,q in towers:\n",
    "            max_q=max(max_q,q)\n",
    "            for newx in range(x-radius,x+radius+1):\n",
    "                for newy in range(y-radius,y+radius+1):\n",
    "                    d=(newx-x)**2+(newy-y)**2\n",
    "                    if d<=radius**2:\n",
    "                        hashmap[(newx,newy)]+=int(q/(1+math.sqrt(d)))\n",
    "        if max_q==0:\n",
    "            return [0,0]\n",
    "        # print(hashmap)\n",
    "        max_x,max_y=-51,-51\n",
    "        max_v=0\n",
    "        for x,y in hashmap:\n",
    "            if hashmap[(x,y)]>max_v:\n",
    "                max_x,max_y=x,y \n",
    "                max_v=hashmap[(x,y)]\n",
    "            elif hashmap[(x,y)]==max_v:\n",
    "                if x<max_x:\n",
    "                    max_x,max_y=x,y \n",
    "                elif x==max_x and y<max_y:\n",
    "                    max_x,max_y=x,y \n",
    "        return max_x,max_y\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
